{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Subsequence of Length K With the Largest Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSubsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到和最大的长度为 K 的子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;。你需要找到&nbsp;<code>nums</code>&nbsp;中长度为 <code>k</code>&nbsp;的 <strong>子序列</strong>&nbsp;，且这个子序列的&nbsp;<strong>和最大&nbsp;</strong>。</p>\n",
    "\n",
    "<p>请你返回 <strong>任意</strong> 一个长度为&nbsp;<code>k</code>&nbsp;的整数子序列。</p>\n",
    "\n",
    "<p><strong>子序列</strong>&nbsp;定义为从一个数组里删除一些元素后，不改变剩下元素的顺序得到的数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,1,3,3], k = 2\n",
    "<b>输出：</b>[3,3]\n",
    "<strong>解释：</strong>\n",
    "子序列有最大和：3 + 3 = 6 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [-1,-2,3,4], k = 3\n",
    "<b>输出：</b>[-1,3,4]\n",
    "<b>解释：</b>\n",
    "子序列有最大和：-1 + 3 + 4 = 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [3,4,3,3], k = 2\n",
    "<b>输出：</b>[3,4]\n",
    "<strong>解释：</strong>\n",
    "子序列有最大和：3 + 4 = 7 。\n",
    "另一个可行的子序列为 [4, 3] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>-10<sup>5</sup>&nbsp;&lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-subsequence-of-length-k-with-the-largest-sum](https://leetcode.cn/problems/find-subsequence-of-length-k-with-the-largest-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-subsequence-of-length-k-with-the-largest-sum](https://leetcode.cn/problems/find-subsequence-of-length-k-with-the-largest-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,3,3]\\n2', '[-1,-2,3,4]\\n3', '[3,4,3,3]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        length = len(nums)\n",
    "        for i in range(length - k):\n",
    "            nums.remove(min(nums))\n",
    "        return nums\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        count = 1\n",
    "        j = len(nums)\n",
    "        while count <= j-k :\n",
    "            num1 = min(nums)\n",
    "            idx = nums.index(num1)\n",
    "            nums.pop(idx)\n",
    "            count += 1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        for _ in range(len(nums) - k):\n",
    "            nums.remove(min(nums))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        f=list(sorted(nums,reverse=True))\n",
    "        d=dict(Counter(f[:k]))\n",
    "        w=[]\n",
    "        for x in nums:\n",
    "            if x in d:\n",
    "                if d[x]>0:\n",
    "                    w.append(x)\n",
    "                    d[x]-=1\n",
    "        return w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "\n",
    "        if k > len(nums):\n",
    "            return []\n",
    "        re = nums[:k]\n",
    "        \n",
    "        for num in nums[k:]:\n",
    "            if num > min(re):\n",
    "                re.remove(min(re))\n",
    "                re.append(num)\n",
    "\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        nums_2 = [i for i in nums[:k]]\n",
    "        for i in nums[k:]:\n",
    "            j = min(nums_2)\n",
    "            if i>j:\n",
    "                nums_2.remove(j)\n",
    "                nums_2.append(i)\n",
    "        return nums_2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        for i in heapq.nsmallest(len(nums) - k, nums):\n",
    "            nums.pop(nums.index(i))\n",
    "       \n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        tmp_List = sorted(nums, reverse=True)\n",
    "        tmp_List = tmp_List[:k]\n",
    "        sub_num = []\n",
    "\n",
    "        for v in nums:\n",
    "            if v in tmp_List:\n",
    "                sub_num.append(v)\n",
    "                tmp_List.remove(v)\n",
    "\n",
    "        return sub_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        arr = sorted(nums, reverse=True)\n",
    "        m = Counter(arr[:k])\n",
    "        ans = []\n",
    "        for x in nums:\n",
    "            if m[x]:\n",
    "                m[x] -= 1\n",
    "                ans.append(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        if k ==0:\n",
    "        #判断k是否为0,为0时返回空数组\n",
    "            return []\n",
    "        #定义新数组为长度为k的升序数组\n",
    "        new_list = sorted(nums)[-k:]\n",
    "        #定义最小值为新数组首个元素\n",
    "        min_val = new_list[0]\n",
    "        nums= [item for item in nums if item >= min_val]\n",
    "        i = 0 \n",
    "        while len(nums) > k:\n",
    "            if nums[i] == min_val:\n",
    "                nums.pop(i)\n",
    "            else:\n",
    "                i += 1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        res=[]\n",
    "        nums1=sorted(nums)[len(nums)-k:len(nums)]\n",
    "        for i in nums:\n",
    "            if i in nums1:\n",
    "                res.append(i)\n",
    "                del nums1[nums1.index(i)]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        num_freq = collections.Counter(sorted(nums, reverse=True)[ :k])\n",
    "        res = []\n",
    "        for x in nums:\n",
    "            if num_freq[x] > 0:\n",
    "                res.append(x)\n",
    "                num_freq[x] -= 1\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        for _ in range(len(nums) - k):\n",
    "            nums.remove(min(nums))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans=[]\n",
    "        temp=sorted(nums)[len(nums)-k:]\n",
    "        dic=dict()\n",
    "        for i in temp:\n",
    "            if i not in dic:\n",
    "                dic[i]=1\n",
    "            else:\n",
    "                dic[i]+=1\n",
    "\n",
    "        for i in nums:\n",
    "            if i in dic and dic[i]>0:\n",
    "                dic[i]-=1\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        if k > len(nums):\n",
    "            return []\n",
    "\n",
    "        if k == len(nums):\n",
    "            return nums\n",
    "\n",
    "        newList = copy.deepcopy(nums)\n",
    "        newList.sort()\n",
    "        newList = newList[:len(nums) - k]\n",
    "        for i in newList:\n",
    "            nums.remove(i)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        new=sorted(nums,reverse=True)\n",
    "        n=new[:k]\n",
    "        dct=collections.Counter(n)\n",
    "        ans=[]\n",
    "        for i in nums:\n",
    "            if i in dct and dct[i]>0:\n",
    "                ans.append(i)\n",
    "                dct[i]-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        nums_copy = [-num for num in nums]\n",
    "        heapq.heapify(nums_copy)\n",
    "        max_k = {}\n",
    "        res = []\n",
    "        # 通过大顶堆获取前k个数\n",
    "        while k>0:\n",
    "            max_temp = heapq.heappop(nums_copy)\n",
    "            if -max_temp not in max_k:\n",
    "                max_k[-max_temp] = 1\n",
    "            else:\n",
    "                max_k[-max_temp] += 1\n",
    "            k -= 1\n",
    "        for num in nums:\n",
    "            if num in max_k and max_k[num]>0:\n",
    "                res.append(num)\n",
    "                max_k[num] -= 1\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in nums:\n",
    "            res.append(i)\n",
    "            if len(res) > k:\n",
    "                res.remove(min(res))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        tmp = []\n",
    "        for i in range(len(nums)):\n",
    "            tmp.append([nums[i],i])\n",
    "        tmp.sort(key=lambda x:x[0],reverse=True)\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(tmp[i])\n",
    "        res.sort(key=lambda x:x[1])\n",
    "        ans = []\n",
    "        for i in range(len(res)):\n",
    "            ans.append(res[i][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        num = nums.copy()\n",
    "        num.sort()\n",
    "        out = len(nums) - k\n",
    "        for i in range(0,out):\n",
    "            a = num[i]\n",
    "            nums.remove(a)\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans = nums.copy()\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(n - k):\n",
    "            ans.remove(nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        if k>=len(nums):\n",
    "            return nums\n",
    "        ans=[]\n",
    "        for i in range(k):\n",
    "            ans.append(nums[i])\n",
    "        for i in range(k,len(nums)):\n",
    "            if nums[i]>min(ans):\n",
    "                del ans[ans.index(min(ans))]\n",
    "                ans.append(nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        a = sorted([(-x,i) for i,x in enumerate(nums)])[:k]\n",
    "        return [-x for x,y in sorted(a, key=lambda x:x[1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        lst = sorted([(v, i) for i, v in enumerate(nums)])\n",
    "        return [a for a, b in sorted(lst[-k:], key=lambda x: x[1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        pos = []\n",
    "        for i, num in enumerate(nums):\n",
    "            pos.append([i, num])\n",
    "        pos.sort(key=lambda row: row[1], reverse=True)\n",
    "        ans = pos[:k]\n",
    "        ans.sort(key=lambda row: row[0])\n",
    "        return [row[1] for row in ans] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=lambda i:-nums[i])\n",
    "        return [nums[x] for x in sorted(idx[:k])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        # 降序\n",
    "        tmp = sorted(nums, reverse=True)\n",
    "        # 前K个最大数对应的字典\n",
    "        dict1 = {}\n",
    "        for i in range(k):\n",
    "            if tmp[i] in dict1:\n",
    "                dict1[tmp[i]] += 1\n",
    "            else:\n",
    "                dict1[tmp[i]] = 1\n",
    "        # 遍历数组，将符合条件的添加到列表中\n",
    "        res = []\n",
    "        for i in nums:\n",
    "            if i in dict1 and dict1[i] > 0:\n",
    "                res.append(i)\n",
    "                dict1[i] -= 1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        for i in range(len(nums) - k):\n",
    "            nums.remove(min(nums))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        num_freq = collections.Counter(sorted(nums)[-k:])\n",
    "        res = []\n",
    "        for x in nums:\n",
    "            if num_freq[x] > 0:\n",
    "                res.append(x)\n",
    "                num_freq[x] -= 1\n",
    "            \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "\n",
    "        if k > len(nums):\n",
    "            return []\n",
    "        heap = []\n",
    "        for i, num in enumerate(nums):\n",
    "            heapq.heappush(heap, (num, i))\n",
    "            if len(heap) > k:\n",
    "                heapq.heappop(heap)\n",
    "        # print(heap)\n",
    "        # re = []\n",
    "        index = []\n",
    "        for (value, idx) in heap:\n",
    "            index.append(idx)\n",
    "        index.sort()\n",
    "        re = [nums[i] for i in index]\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        # 选出最大的k个元素且保持相对位置\n",
    "        n = len(nums)\n",
    "        vals = [[i, nums[i]] for i in range(n)]   # 辅助数组\n",
    "        # 按照数值降序排序，大根堆\n",
    "        vals.sort(key = lambda x: -x[1])\n",
    "        # 取前 k 个并按照下标升序排序\n",
    "        vals = sorted(vals[:k])\n",
    "        res = [val for idx, val in vals]   # 目标子序列\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        S = sum(nums)\n",
    "        N = sorted(nums)\n",
    "        D = Counter()\n",
    "        for i in range(len(nums)-k):\n",
    "            D[N[i]]+=1\n",
    "        pos = 0\n",
    "        while pos < len(nums):\n",
    "            if D[nums[pos]] != 0:\n",
    "                D[nums[pos]] -= 1\n",
    "                nums.pop(pos)\n",
    "            else:\n",
    "                pos += 1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "\n",
    "        if k > len(nums):\n",
    "            return []\n",
    "        heap = []\n",
    "        for i, num in enumerate(nums):\n",
    "            heapq.heappush(heap, (num, i))\n",
    "            if len(heap) > k:\n",
    "                heapq.heappop(heap)\n",
    "        # print(heap)\n",
    "        # re = []\n",
    "        index = []\n",
    "        for (value, idx) in heap:\n",
    "            index.append(idx)\n",
    "        index.sort()\n",
    "        re = [nums[i] for i in index]\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        vals = [[i,nums[i]] for i in range(n)]\n",
    "        vals.sort(key=lambda x:-x[1])\n",
    "        vals = sorted(vals[:k])\n",
    "        res = [val for idx,val in vals]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        num_freq = collections.Counter(sorted(nums, reverse=True)[ :k])\n",
    "        res = []\n",
    "        for x in nums:\n",
    "            if num_freq[x] > 0:\n",
    "                res.append(x)\n",
    "                num_freq[x] -= 1\n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        idx = []\n",
    "        res = []\n",
    "        for _ in range(k):\n",
    "            idx.append(nums.index(max(nums)))\n",
    "            nums[idx[-1]] -= 10**10\n",
    "        idx = sorted(idx)\n",
    "        for i in range(len(idx)):\n",
    "            res.append(nums[idx[i]] + 10**10)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans = [-float('inf') for _ in range(k)]\n",
    "        for num in nums:\n",
    "            if num > min(ans):\n",
    "                del ans[ans.index(min(ans))]\n",
    "                ans.append(num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans = nums[ : k]\n",
    "        for i in range(k, len(nums)):\n",
    "            tmp = min(ans)\n",
    "            if nums[i] > tmp:\n",
    "                ans.remove(tmp)\n",
    "                ans.append(nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic = {}\n",
    "        for i, v in enumerate(nums):\n",
    "            if v not in dic:\n",
    "                dic[v] = [i]\n",
    "            else:\n",
    "                dic[v].append(i)\n",
    "        nums.sort()\n",
    "        lst = []\n",
    "        for n in nums[-k:]:\n",
    "            lst.append((dic[n][-1], n))\n",
    "            dic[n].pop()\n",
    "        lst.sort()\n",
    "        return [b for a, b in lst]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        heap = []\n",
    "        for i, num in enumerate(nums):\n",
    "            if len(heap) < k:\n",
    "                heapq.heappush(heap, (num, i))\n",
    "            elif num > heap[0][0]:\n",
    "                heapq.heapreplace(heap, (num, i))\n",
    "        heap.sort(key = lambda x: x[1])\n",
    "        return [i[0] for i in heap]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        # 选出最大的k个元素且保持相对位置\n",
    "        n = len(nums)\n",
    "        vals = [[i, nums[i]] for i in range(n)]   # 辅助数组\n",
    "        # 按照数值降序排序，大根堆\n",
    "        vals.sort(key = lambda x: -x[1])\n",
    "        # 取前 k 个并按照下标升序排序，默认是按照第一个元素的大小做比较\n",
    "        vals = sorted(vals[:k])\n",
    "        res = [val for idx, val in vals]   # 目标子序列\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        rank = sorted(range(len(nums)), key = nums.__getitem__)\n",
    "        ans = sorted(rank[-k:])\n",
    "        return [nums[i] for i in ans]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans = [-float('inf') for _ in range(k)]\n",
    "        for num in nums:\n",
    "            if num > min(ans):\n",
    "                del ans[ans.index(min(ans))]\n",
    "                ans.append(num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        vals = [[i, nums[i]] for i in range(n)]   # 辅助数组\n",
    "        # 按照数值降序排序\n",
    "        vals.sort(key = lambda x: -x[1])\n",
    "        # 取前 k 个并按照下标升序排序\n",
    "        vals = sorted(vals[:k])\n",
    "        res = [val for idx, val in vals]   # 目标子序列\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        items = [(num, i) for i, num in enumerate(nums)]\n",
    "        items.sort(reverse=True)\n",
    "        items = items[:k]\n",
    "        items.sort(key=lambda x:x[1])\n",
    "        return [num for (num, i) in items]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        rank = [*range(len(nums))]\n",
    "        rank.sort(key = lambda i: nums[i])\n",
    "        ans = sorted(rank[-k:])\n",
    "        return [nums[i] for i in ans]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\r\n",
    "        result = nums[:k]\r\n",
    "        min_result = min(result)\r\n",
    "        for i in range(k,len(nums)):\r\n",
    "            if nums[i] > min_result:\r\n",
    "                result.remove(min_result)\r\n",
    "                result.append(nums[i])\r\n",
    "                min_result = min(result)\r\n",
    "        return result\r\n",
    "\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        vals = [[i,nums[i]] for i in range(n)]\n",
    "        vals.sort(key=lambda x:-x[1])\n",
    "        vals = sorted(vals[:k])\n",
    "        res = [val for idx,val in vals]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        vals =[[i,nums[i]]for i in range(n)]\n",
    "        vals.sort(key=lambda x:-x[1])\n",
    "        vals=sorted(vals[:k])\n",
    "        res=[val for idx,val in vals]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        retVal = []\n",
    "\n",
    "        sequence = [[index, value] for index, value in enumerate(nums)]\n",
    "        sequence.sort(key=lambda sequence: -sequence[1])\n",
    "        sequence = sequence[:k]\n",
    "        sequence.sort(key=lambda sequence: sequence[0])\n",
    "        retVal = [value for _, value in sequence]\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        nums = [(i, n) for i, n in enumerate(nums)]\n",
    "        nums.sort(key=lambda x: x[1])\n",
    "        nums = nums[-k:]\n",
    "        nums.sort(key=lambda x: x[0])\n",
    "        return [n for _, n in nums]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        # 删除 len - k 个最小值字符\n",
    "        loop = len(nums) - k\n",
    "        for _ in range(loop):\n",
    "            min_val = 10 ** 5 + 1\n",
    "            min_index = -1\n",
    "            for i, n in enumerate(nums):\n",
    "                if n < min_val:\n",
    "                    min_index = i\n",
    "                    min_val = n\n",
    "            nums.pop(min_index)\n",
    "        print(nums)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        heap = []\n",
    "        i, n = 0, len(nums)\n",
    "        while i < n:\n",
    "            heappush(heap, (nums[i], i))\n",
    "            if len(heap) > k:\n",
    "                heappop(heap)\n",
    "            i += 1\n",
    "        heap.sort(key = lambda x: x[1])\n",
    "        return [val for val, idx in heap]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        return [x for _, x in sorted(sorted(enumerate(nums), key=lambda x: -x[1])[:k])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        vals = [[i, nums[i]] for i in range(n)]\n",
    "        vals.sort(key = lambda x: -x[1])\n",
    "        vals = sorted(vals[:k])\n",
    "        res = [val for idx, val in vals]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        tmp={i:v for i,v in enumerate(nums)}\n",
    "        tmp=sorted(tmp.items(), key=lambda x:x[1], reverse=True)\n",
    "        res=[i[0] for i in tmp[:k]]\n",
    "        res.sort()\n",
    "        return [nums[i] for i in res]\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        heap = []\n",
    "        for i, num in enumerate(nums):\n",
    "            if len(heap) < k:\n",
    "                heapq.heappush(heap, (num, i))\n",
    "            elif num > heap[0][0]:\n",
    "                heapq.heapreplace(heap, (num, i))\n",
    "        heap.sort(key = lambda x: x[1])\n",
    "        return [i[0] for i in heap]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        return [x for _,x in sorted(sorted(enumerate(nums),key=lambda p:p[1])[-k:])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        hash_L = [[i,v]for i,v in enumerate(nums)]\n",
    "        hash_L_sort = sorted(hash_L,key = lambda x:-x[1])[0:k]\n",
    "        hash_L_sort.sort(key=lambda x:x[0])\n",
    "        return [v for i,v in hash_L_sort]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        return [x for _, x in sorted(sorted(enumerate(nums), key=lambda x: -x[1])[:k], key=lambda x: x[0])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        hp=[-i for i in nums]\n",
    "        heapq.heapify(hp)\n",
    "        res=[]\n",
    "        for i in range(k):\n",
    "            res.append(-heapq.heappop(hp))\n",
    "        dic={}\n",
    "        #print(res) #[4, 3, -1]\n",
    "        num=0\n",
    "        for index,item in enumerate(nums):\n",
    "            if item in res:\n",
    "                dic[index]=item\n",
    "                num+=1\n",
    "                res.remove(item) \n",
    "        list1=sorted(dic.items(),key=lambda x:x[0] )\n",
    "        ress=[]\n",
    "        for i in range(0,len(list1)):\n",
    "            ress.append(list1[i][1])\n",
    "        return ress"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums);\n",
    "        tmp = [ [i, nums[i]] for i in range(n)];\n",
    "        tmp.sort(key = lambda x : -x[1])\n",
    "        tmp = sorted(tmp[:k]);\n",
    "        res = [v for i, v in tmp];\n",
    "        return res;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        rank = [*range(len(nums))]\n",
    "        rank.sort(key = lambda i: -nums[i])\n",
    "        ans = sorted(rank[:k])\n",
    "        return [nums[i] for i in ans]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        nums1 = sorted([(num, i) for i, num in enumerate(nums)], reverse=True)\n",
    "        return [nums[i] for i in sorted([i for _, i in nums1[:k]])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        h = set(i for num, i in sorted([(num, i) for i, num in enumerate(nums)], reverse=True)[:k])\n",
    "        return [num for i, num in enumerate(nums) if i in h]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [[idx, nums[idx]] for idx in range(n)]\n",
    "        res.sort(key = lambda x : x[1])\n",
    "        vals = sorted(res[-k:])\n",
    "        return [val for idx, val in vals]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        vals = [[i, nums[i]] for i in range(n)]\n",
    "        vals.sort(key=lambda x:-x[1])\n",
    "        vals = sorted(vals[:k])\n",
    "        res = [val for idx, val in vals]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        res = sorted([a for a in sorted(enumerate(nums), key=lambda x: -x[1])][:k], key=lambda x: x[0])\n",
    "        return [r[1] for r in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        nums1 = list(enumerate(nums))     # 先获取索引和对应值的元组\n",
    "        nums2 = sorted(nums1, key=lambda x: x[1])   # 对值进行排序\n",
    "        nums3 = nums2[len(nums) - k:]               # 取出长度为k的值最大的三个数\n",
    "        res = sorted(nums3, key=lambda x: x[0])     # 对取出值的元组按索引从小到大进行排序，让他返回到在原数组中的顺序\n",
    "        result = [x[1] for x in res]                # 取出每个元组的值\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        h = set(i for num, i in sorted([(num, i) for i, num in enumerate(nums)], reverse=True)[:k])\n",
    "        return [num for i, num in enumerate(nums) if i in h]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxSubsequence(self, nums, k):\n",
    "        a=sorted(zip(nums,range(len(nums))))\n",
    "        b=a[-k:]\n",
    "        b.sort(key=lambda x:x[1])\n",
    "        ans=[]\n",
    "        for x,_ in b:\n",
    "            ans.append(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        data = {}\n",
    "        for idx, one in enumerate(nums):\n",
    "            data[idx] = one\n",
    "        res = sorted(data.items(), key=lambda one: -one[1])\n",
    "        result = []\n",
    "        for a, b in res:\n",
    "            result.append([a, b])\n",
    "            if len(result) == k:\n",
    "                break\n",
    "        return [_[1] for _ in sorted(result, key=lambda one: one[0])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        return [i[0] for i in sorted(sorted([(num, idx) for idx, num in enumerate(nums)])[-k:], key=lambda x: x[1])]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans = sorted(enumerate(nums), key=lambda x: -x[1])\n",
    "        res = sorted([a for a in ans][:k], key=lambda x: x[0])\n",
    "        return [r[1] for r in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        vals = [[i, nums[i]] for i in range(n)]   # 辅助数组\n",
    "        # 按照数值降序排序\n",
    "        vals.sort(key = lambda x: -x[1])\n",
    "        # 取前 k 个并按照下标升序排序\n",
    "        vals = sorted(vals[:k])\n",
    "        res = [val for idx, val in vals]   # 目标子序列\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n",
    "        hash_L = [[i,v]for i,v in enumerate(nums)]\n",
    "        hash_L_sort = sorted(hash_L,key = lambda x:-x[1])[0:k]\n",
    "        hash_L_sort.sort(key=lambda x:x[0])\n",
    "        return [v for i,v in hash_L_sort]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubsequence(self, nums: list[int], k: int) -> list[int]:\n",
    "        index = range(len(nums))\n",
    "        nums,index = zip(*sorted(zip(nums, index),reverse=True))\n",
    "        nums = nums[0:k]\n",
    "        index = index[0:k]\n",
    "        index,nums = zip(*sorted(zip(index,nums)))\n",
    "        return nums"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
